package wtx.leetcode;

import java.util.List;
import java.util.ArrayList;;

class MaxProfitIV {
  List<Integer> peekPos = new ArrayList<>();
  List<Integer> vallayPos = new ArrayList<>();
  List<List<Integer>> potentialMaxprofit;
  List<List<Integer>> posPmp;
  public int maxProfit(int k, int[] prices) {
    if (k == 0 || prices == null || prices.length < 2) {
      return 0;
    }
    int periodLen = prices.length;
    potentialMaxprofit = new ArrayList<>(k);
    posPmp = new ArrayList<>(k);
    peekPos.clear();
    vallayPos.clear();
    initPeekAfter(prices, periodLen);
    return max_profit(k, prices);
  }
  private int max_profit(int K, int[] prices) {
    int retMax = 0;
    int vi = -1;
    for (int k = 1; k <= K; ++k) {
      potentialMaxprofit.add(new ArrayList<>());
      potentialMaxprofit.get(k).add(-1);
      posPmp.add(new ArrayList<>());
      final int N = potentialMaxprofit.get(k-1).size();
      int thisKmax = 0;
      for (int i = 1; i < N; ++i) {
        int lastMaxpos = posPmp.get(k-1).get(i-1);
        int lastPotential = potentialMaxprofit.get(k-1).get(lastMaxpos);
        if (lastPotential > 0 && i + vi < vallayPos.size()) {
          int candidate = lastPotential - prices[vallayPos.get(i+vi)];
          if (candidate > thisKmax) {
            thisKmax = candidate;
          }
          int lastMaxMp = lastOf(potentialMaxprofit.get(k));
          if (i+vi+1 < peekPos.size()) {
            int potential = prices[peekPos.get(i+vi+1)] + thisKmax;
            if (lastMaxMp < potential) {
              potentialMaxprofit.get(k).add(potential);
              posPmp.get(k).add(potentialMaxprofit.get(k).size() - 1);
            } else {
              potentialMaxprofit.get(k).add(lastMaxMp);
              posPmp.get(k).add(lastOf(posPmp.get(k)));
            }
          }
        }
      }
      vi += 1;
      if (thisKmax > retMax) {
        retMax = thisKmax;
      }
    }
    return retMax;
  }
  private void initPeekAfter(int[] prices, final int N) {
    int peekAfter = 0;
    potentialMaxprofit.add(new ArrayList<>());
    potentialMaxprofit.get(0).add(-1);
    posPmp.add(new ArrayList<>());
    posPmp.get(0);
    int prev = -1;
    for (int i = N-1; i > 0; --i) {
      if (prices[i] > prices[i-1] && prices[i] >= prev) {
        // find peek
        peekPos.add(i);
        peekAfter = Math.max(peekAfter, prices[i]);
      } 
      if (prices[i] <= prices[i-1] && prices[i] < prev) {
        vallayPos.add(i);
        int tmp = peekAfter; 
        int lastMaxMp = lastOf(potentialMaxprofit.get(0));
        if (tmp > lastMaxMp) {
          potentialMaxprofit.get(0).add(tmp);
          posPmp.get(0).add(potentialMaxprofit.get(0).size()-1);
        } else {
          potentialMaxprofit.get(0).add(lastMaxMp);
          posPmp.get(0).add(lastOf(posPmp.get(0)));
        }
      }
      prev = prices[i];
    }
    if (prices[0] < prices[1]) {
      vallayPos.add(0);
      int tmp = peekAfter;
      int lastMaxMp = lastOf(potentialMaxprofit.get(0));
      if (tmp > lastMaxMp) {
        potentialMaxprofit.get(0).add(tmp);
        posPmp.get(0).add(potentialMaxprofit.get(0).size()-1);
      } else {
        potentialMaxprofit.get(0).add(lastMaxMp);
        posPmp.get(0).add(lastOf(posPmp.get(0)));
      }
    }
  }
  private int lastOf(List<Integer> ll) {
    return ll.get(ll.size()-1);
  }
}